#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (const auto& e : nums) sum += e;
        if (sum & 1) return false;
        int tgt = sum >> 1;
        int n = nums.size();
        // vector<vector<bool>> dp(n + 1, vector<bool>(tgt + 1));
        // for(auto& e : dp) e[0] = true;
        // for(int i = 1; i <= n; i++)
        // {
        //     int cur = nums[i - 1];
        //     for(int j = 1; j <= tgt; j++)
        //     {
        //         dp[i][j] = dp[i - 1][j];
        //         if(j >= cur)
        //             dp[i][j] = dp[i][j] || dp[i - 1][j - cur];
        //     }
        //     if(dp[i][tgt]) return true;
        // }
        vector<bool> dp(tgt + 1);
        dp[0] = true;
        for (int i = 1; i <= n; i++)
        {
            int cur = nums[i - 1];
            for (int j = tgt; j >= cur; j--)
                dp[j] = dp[j] || dp[j - cur];
            if (dp[tgt]) return true;
        }
        return false;
    }
};